package com.sicheng.lc.周赛.分类.并差集;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/14 21:16
 */
public class 统计封闭岛屿的数目 {
    //https://leetcode.cn/problems/number-of-closed-islands/

    int[] p;
    int cnt, m, n;

    // 初始化 cnt 只记录grid 非边界的0 , 连通时非边界的0向四周连
    void init(int[][] grid) {
        p = new int[m * n];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i != 0 && i != m - 1 && j != 0 && j != n - 1 && grid[i][j] == 0) {
                    cnt++;
                    p[get(i, j)] = get(i, j);
                }
            }

        }
    }

    int find(int x) {
        if (x == p[x])
            return x;
        return p[x] = find(p[x]);
    }

    void union(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
            cnt--;
        }

    }

    public int get(int i, int j) {
        return i * n + j;
    }

    public int closedIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        init(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i != 0 && i != m - 1 && j != 0 && j != n - 1 && grid[i][j] == 0) {
                    grid[i][j] = 1;
                    if (grid[i - 1][j] == 0)
                        union(get(i, j), get(i - 1, j));
                    if (grid[i][j - 1] == 0)
                        union(get(i, j), get(i, j - 1));
                    if (grid[i][j + 1] == 0)
                        union(get(i, j), get(i, j + 1));
                    if (grid[i + 1][j] == 0)
                        union(get(i, j), get(i + 1, j));
                }
            }
        }
        return cnt;
    }
}
